package com.shangxia.leetcode.hoot100.easy;

import com.alibaba.fastjson.JSONObject;
import com.shangxia.leetcode.hoot100.easy.bean.ListNode;
import com.shangxia.leetcode.hoot100.easy.bean.TreeNode;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;


import java.util.*;

/**
 * @ProjectName: leetcode
 * @ClassName: Solution1
 * @Time: 2020/11/21
 * @Author: zhouy
 * @Description:
 * @Experience:
 */

@Slf4j
public class Solution1 {
    public static void main(String[] args) {
        System.out.println(isValid("(){}[]"));
        int[] nums = {2, 7, 11, 15};
        int[] nums2 = {2, 11, 11, 4, 2};
        int target = 18;
        System.out.println("twoSum " + JSONObject.toJSONString(twoSum(nums, target)));
        System.out.println("singleNumber " + JSONObject.toJSONString(singleNumber(nums2)));

        System.out.println("反转链表");
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
        System.out.println(JSONObject.toJSONString(listNode));
        System.out.println(JSONObject.toJSONString(reverseList(listNode)));
    }


    /**
     * 20 有效的括号
     *
     * @param s
     * @return
     * @Description: 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
     * 有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 注意空字符串可被认为是有效字符串。
     */
    public static boolean isValid(String s) {
        if (null == s) {
            return false;
        }
        if ("".equals(s)) {
            return true;
        }
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case '(':
                case '[':
                case '{':
                    list.add(s.charAt(i));
                    break;
                case ')':
                    if (list.size() == 0) {
                        return false;
                    }
                    if (list.get(list.size() - 1) == '(') {
                        list.remove(list.size() - 1);
                    } else {
                        list.add(')');
                    }
                    break;
                case ']':
                    if (list.size() == 0) {
                        return false;
                    }
                    if (list.get(list.size() - 1) == '[') {
                        list.remove(list.size() - 1);
                    } else {
                        list.add('[');
                    }
                    break;
                case '}':
                    if (list.size() == 0) {
                        return false;
                    }
                    if (list.get(list.size() - 1) == '{') {
                        list.remove(list.size() - 1);
                    } else {
                        list.add('}');
                    }
                    break;
                default:
                    return false;
            }

        }
        if (list.size() == 0) {
            return true;
        }
        return false;
    }

    /**
     * 1 两数之和
     *
     * @param nums
     * @param target
     * @return
     * @Description:给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
     */
    public static int[] twoSum(int[] nums, int target) {
        if (ObjectUtils.isEmpty(nums) || nums.length < 2) {
            return null;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = target - nums[i];
            if (!map.containsKey(nums[i])) {
                map.put(num, i);
            } else {
                return new int[]{map.get(nums[i]), 1};
            }
        }
        return null;
    }

    /**
     * 101 对称二叉树
     *
     * @param root
     * @return
     * @Description:给定一个二叉树，检查它是否是镜像对称的。
     */
    public static boolean isSymmetric(TreeNode root) {
        return isMirror(root.getLeft(), root.getRight());
    }

    private static boolean isMirror(TreeNode left, TreeNode right) {
        if (ObjectUtils.isEmpty(left) && ObjectUtils.isEmpty(right)) {
            return true;
        }
        if (ObjectUtils.isEmpty(left) || ObjectUtils.isEmpty(right)) {
            return false;
        }
        return left.getVal() == right.getVal() && isMirror(left.getLeft(), right.getRight()) && isMirror(left.getLeft(), right.getLeft());
    }

    /**
     * 136 只出现一次的数字
     *
     * @param nums
     * @return
     * @Description:给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 异或运算的使用
     */
    public static int singleNumber(int[] nums) {
        if (ObjectUtils.isEmpty(nums)) {
            return 0;
        }
        int num = nums[0];
        for (int i = 1; i < nums.length; i++) {
            num = num ^ nums[i];
        }
        return num;
    }

    /**
     * 206. 反转链表
     *
     * @param head
     * @return
     * @Description:反转一个单链表。
     */
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.getNext();
            curr.setNext(prev);
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public ListNode reverseList2(ListNode head) {
        //递归终止条件是当前为空，或者下一个节点为空
        if (head == null || head.getNext() == null) {
            return head;
        }
        //这里的cur就是最后一个节点
        ListNode cur = reverseList2(head.getNext());
        //这里请配合动画演示理解
        //如果链表是 1->2->3->4->5，那么此时的cur就是5
        //而head是4，head的下一个是5，下下一个是空
        //所以head.next.next 就是5->4
        head.getNext().setNext(head);
        //防止链表循环，需要将head.next设置为空
        head.setNext(null);
        //每层递归函数都返回cur，也就是最后一个节点
        return cur;
    }

}
